GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Blockcode</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Blockcode</h1>

</header>

</div>

Blockcodes sind eine Art der <a href="Kanalkodierung" title="Kanalkodierung">Kanalkodierung</a> der Familie der (fehlererkennenden und) <a href="Vorw%C3%A4rtsfehlerkorrektur" title="Vorwärtsfehlerkorrektur">fehlerkorrigierenden Codes</a>. Sie zeichnen sich durch eine feste Blockgröße aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> <a href="Symbol_(Nachrichtentechnik)" title="Symbol (Nachrichtentechnik)">Symbolen</a> eines festen <a href="Alphabet_(Informatik)" title="Alphabet (Informatik)">Alphabets</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> (bei <a href="Bin%C3%A4rcode" title="Binärcode">Binärcodes</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma =\{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma =\{0,1\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9b63c023355713e4b16a56276b6497d4b32a0c32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle \Sigma =\{0,1\}}" loading="lazy">) aus. Einzelne Blocks werden im Gegensatz zu <a href="Faltungscode" title="Faltungscode">Faltungscodes</a> unabhängig voneinander kodiert und dekodiert.

Wichtige Eigenschaften eines Blockcodes sind die <a href="Informationsrate" title="Informationsrate">Informationsrate</a> (das Verhältnis aus enthaltener Informationsmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> zur Gesamt-Datenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">) sowie seine Korrekturrate (d. h. die Fähigkeit Fehler zu erkennen und/oder zu korrigieren). Beide Eigenschaften beeinflussen einander und spannen eine gemeinsame, unüberwindbare Schranke auf. Durch Optimierung kann man sich der Schranke nähern, erhält aber lange und <a href="NP_(Komplexit%C3%A4tsklasse)" title="NP (Komplexitätsklasse)">aufwändig</a> zu dekodierende Codes. Hier hat sich das Kaskadieren von Codes als praktikablere Lösung erwiesen.

Obwohl Blockcodes häufig nicht optimal im Sinne einer minimalen mittleren Codewortlänge sind, schränkt man sich oft auf Blockcodes ein. Eine weitere Spezialisierung stellen <a href="Linearer_Code" title="Linearer Code">lineare Codes</a> und <a href="Systematischer_Code" title="Systematischer Code">systematische Codes</a> dar.

<div class="mw-heading mw-heading2"><h2 id="Aufbau">Aufbau</h2></div>

Aus dem Alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> und der Blockgröße <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ergibt sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e52398b6b9103472077e244c7db84eaeab4accdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{n}}" loading="lazy"> als Menge der möglichen Worte, von denen eine Teilmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4bac6e99f5cb83e2f634755e5be40520816641e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.234ex; height:2.509ex;" alt="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}" loading="lazy"> die gültigen Codeworte darstellt. Die Mächtigkeit des Alphabets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> wird mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=|\Sigma |}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=|\Sigma |}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b97097334b2ead54b0ec3035dc095a11db878d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.14ex; height:2.843ex;" alt="{\displaystyle q=|\Sigma |}" loading="lazy"> bezeichnet, sie beträgt im Falle von Binärcodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=|\Sigma |=2}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=|\Sigma |=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c400de3f2a4938137b6416869704a059cbf3955.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.401ex; height:2.843ex;" alt="{\displaystyle q=|\Sigma |=2}" loading="lazy">.

Die Mächtigkeit des Codes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdb08d532e1fc4ab01ec67f37082fef36f051caf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.533ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {C}}|}" loading="lazy"> kann bei vielen Codes (bei linearen Codes immer) als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=q^{k}}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=q^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9a862e2f614ff1ff277c780e48cecb5f926d65de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.799ex; height:3.176ex;" alt="{\displaystyle |{\mathcal {C}}|=q^{k}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in \mathbb {N} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in \mathbb {N} ^{+}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c8abd3366b703d9dc620115174fe692aeb5ded4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.241ex; height:2.509ex;" alt="{\displaystyle k\in \mathbb {N} ^{+}}" loading="lazy"> geschrieben werden. Diese Codes können bei einer Blockgröße von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Symbolen eine Nutzlast <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\leq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\leq n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/621f658bb51d7caac329d29e9bf435361813777f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.704ex; height:2.343ex;" alt="{\displaystyle k\leq n}" loading="lazy"> tragen.

Die Informationrate beträgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k/n\leq 1}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k/n\leq 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4004b824de8adfe3e208980cfbc43215072cae8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.029ex; height:2.843ex;" alt="{\displaystyle k/n\leq 1}" loading="lazy">, die Korrekturrate wird durch den (minimalen) Hamming-Abstand des Codes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> limitiert. Der <a href="Hamming-Abstand" title="Hamming-Abstand">Hamming-Abstand</a> zweier Codeworte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01acb7953ba52c2aa44264b5d0f8fd223aa178a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a844d180d176af828d1636d4e85aa534d0b77baa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.917ex; height:2.343ex;" alt="{\displaystyle c_{j}}" loading="lazy"> ist hierbei die Anzahl unterschiedlicher Symbole dieser Codeworte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (c_{i},c_{j})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (c_{i},c_{j})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9a658dfb4df58d16ee71b617d5167f3f7fad5840.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.502ex; height:3.009ex;" alt="{\displaystyle \Delta (c_{i},c_{j})}" loading="lazy">, der (minimale) Hamming-Abstand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> eines (ganzen) Codes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> ist der minimale Hamming-Abstand aller (disjunkten) Codewort-Paare, d. h. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=\Delta ({\mathcal {C}})\,\,{\overset {\underset {\mathrm {def} }{}}{=}}\,\min _{i\neq j}\,\Delta (c_{i},c_{j})}">

</mrow>

<mover>

</mrow>

</munder>

</mover>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\Delta ({\mathcal {C}})\,\,{\overset {\underset {\mathrm {def} }{}}{=}}\,\min _{i\neq j}\,\Delta (c_{i},c_{j})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d5c2cdca3d985067ab54c858c8fd2927f04959e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:25.83ex; height:5.343ex;" alt="{\displaystyle d=\Delta ({\mathcal {C}})\,\,{\overset {\underset {\mathrm {def} }{}}{=}}\,\min _{i\neq j}\,\Delta (c_{i},c_{j})}" loading="lazy">. Letztere beschränkt die maximale (zuverlässige) Korrekturleistung auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> Symbolfehlern mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=\left\lfloor (d-1)/2\right\rfloor }">

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=\left\lfloor (d-1)/2\right\rfloor }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4022b1ccc8a6a6e8f15dad4f6244b081cbf7fef1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.356ex; height:2.843ex;" alt="{\displaystyle t=\left\lfloor (d-1)/2\right\rfloor }" loading="lazy"> ein. Bei kaskadierten Korrekturverfahren spielt neben der Fehlerkorrektur auch die Fehlererkennung eine Rolle. Zum einen erkennen Nicht-<a href="Perfekter_Code" title="Perfekter Code">perfekte Codes</a> eine gewisse Menge an Mehrbit-Fehler mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{\mathrm {Mehrbit} }>t}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{\mathrm {Mehrbit} }>t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b9e8b0c2725654bb64edbd98a12f45530329949.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.816ex; height:2.343ex;" alt="{\displaystyle t_{\mathrm {Mehrbit} }>t}" loading="lazy">, die sie selbst nicht mehr korrigieren können, zum anderen kann man Fehlerkorrektur-Fähigkeiten gegen weitere (garantierte) Fehlererkennungs-Fähigkeiten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> eintauschen und damit folgende Korrektur-Stufen unterstützen: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=d-1-t_{\mathrm {benutzt} }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=d-1-t_{\mathrm {benutzt} }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/612c80eaee41491db76d66930dca7762def3df77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.759ex; height:2.509ex;" alt="{\displaystyle r=d-1-t_{\mathrm {benutzt} }}" loading="lazy">.

Für Codes haben sich in der Literatur unterschiedliche Notationen etabliert:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k;d,q]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3a9a0988ef325f77d93553b46afd8e3c52c07317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.287ex; height:2.843ex;" alt="{\displaystyle [n,k;d,q]}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k;d]_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k;d]_{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec6c9dfccf00c353b46f562a9bed488610a16262.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.172ex; height:3.009ex;" alt="{\displaystyle [n,k;d]_{q}}" loading="lazy">, häufig wird das Semikolon durch ein Komma ersetzt, die eckigen Klammern durch runde Klammern. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/26622af6012fb982cab4e9584f57dd4f364233b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=2}" loading="lazy"> wird häufig weggelassen, gleiches gilt für das <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/58a4a6128b5cc1e25fcba3a16cbd9126b2d3e2fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.477ex; height:2.176ex;" alt="{\displaystyle d=3}" loading="lazy"> der klassischen Hamming-Codes.</li>

<li>Häufig wird statt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> (der Anzahl der Nutzsymbole) die Mächtigkeit des Codes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{k}=|{\mathcal {C}}|}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{k}=|{\mathcal {C}}|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6002dfe6fd6daa8ae3ff2cdfef67dbfc62b4904e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.799ex; height:3.176ex;" alt="{\displaystyle q^{k}=|{\mathcal {C}}|}" loading="lazy">, d. h. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,q^{k},d)_{q}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,q^{k},d)_{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a33c80123332be76d33c325e288d9c0fd4014a80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.644ex; height:3.343ex;" alt="{\displaystyle (n,q^{k},d)_{q}}" loading="lazy"> oder der Code selbst angegeben <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,{\mathcal {C}},d)_{q}}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,{\mathcal {C}},d)_{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/451d53750564ac20c52a9721eb05613e7d0c07be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.715ex; height:3.009ex;" alt="{\displaystyle (n,{\mathcal {C}},d)_{q}}" loading="lazy"> angegeben, zum Teil wird diese Information in der Art der verwendeten Klammern versteckt.</li></ul>

Im Weiteren wird versucht, dies wie auch die Nutzung von Variablennamen sowohl in diesem Artikel wie auch in verwandten Artikeln konsistent zu halten.

Man bezeichnet allgemein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> als einen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,{\mathcal {C}};d,q)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,{\mathcal {C}};d,q)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31551b4957ef0aa33b0d7b31c85eed72f4b2a3d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.83ex; height:2.843ex;" alt="{\displaystyle (n,{\mathcal {C}};d,q)}" loading="lazy">-Code, falls

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> ein Alphabet mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Sigma |=q}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Sigma |=q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0abd464fb116fdb3e3fb42d83a9a65ca3b982c18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.14ex; height:2.843ex;" alt="{\displaystyle |\Sigma |=q}" loading="lazy"> ist,</li>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4bac6e99f5cb83e2f634755e5be40520816641e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.234ex; height:2.509ex;" alt="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}" loading="lazy"> ist und</li>

<li>der (minimalen) Hamming-Abstand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=\Delta ({\mathcal {C}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\Delta ({\mathcal {C}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/888af9ca0a02cdd9e3d0d45a46f9dd4867f21de5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.299ex; height:2.843ex;" alt="{\displaystyle d=\Delta ({\mathcal {C}})}" loading="lazy"> ist.</li></ul>

Betrachtet man <a href="Linearer_Code" title="Linearer Code">lineare Codes</a>, so spricht man von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k;d,q]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k;d,q]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3a9a0988ef325f77d93553b46afd8e3c52c07317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.287ex; height:2.843ex;" alt="{\displaystyle [n,k;d,q]}" loading="lazy">-Codes bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k;d]_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k;d]_{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec6c9dfccf00c353b46f562a9bed488610a16262.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.172ex; height:3.009ex;" alt="{\displaystyle [n,k;d]_{q}}" loading="lazy">-Codes,

wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> hier die Dimension von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> über dem <a href="Endlicher_K%C3%B6rper" title="Endlicher Körper">Körper <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dbb96e056c071d13fc7702013f9273e7f5cd88a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.409ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{q}}" loading="lazy"></a> ist. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> haben dabei die gleiche Bedeutung wie bei den allgemeinen Blockcodes.

Man interessiert sich bei gegebenem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> für eine Maximierung der Mächtigkeit des Codes, d. h. für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max\{|{\mathcal {C}}|:{\mathcal {C}}\,\,{\mathrm {mit} }\,\,\Delta ({\mathcal {C}})\geq d\}}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max\{|{\mathcal {C}}|:{\mathcal {C}}\,\,{\mathrm {mit} }\,\,\Delta ({\mathcal {C}})\geq d\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4570caccfbb912a15d32ac9016b3bbe2400c5718.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.694ex; height:2.843ex;" alt="{\displaystyle \max\{|{\mathcal {C}}|:{\mathcal {C}}\,\,{\mathrm {mit} }\,\,\Delta ({\mathcal {C}})\geq d\}}" loading="lazy">, da hierbei eine optimale Informationsrate für diese Parameter erzielt wird.

Allerdings gibt es günstige Parameter, die zu effizienteren Codes als ihre Nachbarparameter führen.

So fordert ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [23,12;7,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [23,12;7,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71d94bdcff52e3ce3b8b9de229b3e9049c8ee73a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.37ex; height:2.843ex;" alt="{\displaystyle [23,12;7,2]}" loading="lazy">-Code 11 Schutzbits, ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [27,13;7,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [27,13;7,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f6925005f577d390cd6414c92061411488110f51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.37ex; height:2.843ex;" alt="{\displaystyle [27,13;7,2]}" loading="lazy">-Code allerdings schon 14.

Ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [41,24;7,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [41,24;7,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e302abf2d0d8bfaf5cd0eacb9b2e7148a041129e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.37ex; height:2.843ex;" alt="{\displaystyle [41,24;7,2]}" loading="lazy">- kommt wie ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [55,38;7,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [55,38;7,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/78d98aeab7026fdfcc7fa2bc107503252da688f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.37ex; height:2.843ex;" alt="{\displaystyle [55,38;7,2]}" loading="lazy">-Code mit 17 Schutzbits aus.

Es gibt Abschätzungen, ob Codes möglich sein könnten oder gegen gewisse Prinzipien verstoßen:

<ul><li><a href="Singleton-Schranke" title="Singleton-Schranke">Singleton-Schranke</a> (<a href="MDS-Code" title="MDS-Code">MDS-Code</a>)</li>

<li><a href="Hamming-Schranke" class="mw-redirect" title="Hamming-Schranke">Hamming-Schranke</a> (<a href="Perfekter_Code" title="Perfekter Code">Perfekter Code</a>)</li>

<li><a href="Plotkin-Grenze" title="Plotkin-Grenze">Plotkin-Schranke</a></li>

<li><a href="Gilbert-Varshamov-Schranke" title="Gilbert-Varshamov-Schranke">Gilbert-Varshamov-Schranke</a>, Johnson-Schranke, Griesmer-Schranke, Bassalygo-Elias-Schranke</li>

<li><a href="Optimaler_Code" title="Optimaler Code">Optimaler Code</a></li></ul>

Schranken weisen darauf hin, ob Codes existieren können, nicht ob sie konstruierbar sind und wirklich existieren.

<div class="mw-heading mw-heading2"><h2 id="Typen_von_Blockcodes">Typen von Blockcodes</h2></div>

Formal heißt der Code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4bac6e99f5cb83e2f634755e5be40520816641e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.234ex; height:2.509ex;" alt="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}" loading="lazy"> Blockcode, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> als Alphabet bezeichnet wird und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> die Länge jedes Codewortes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d67240ce3f564bd39e61e340509abe02b0373f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.087ex; height:2.176ex;" alt="{\displaystyle c\in {\mathcal {C}}}" loading="lazy"> ist.

Triviale Blockcodes sind Codes

<ul><li>die nur ein Wort als Code umfassen: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=1}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5f4dfad6cf74dabd8d92e7b0dba7a66cfeedca8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.794ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {C}}|=1}" loading="lazy">. Es lassen sich alle Übertragungsfehler erkennen, aber keine Information übertragen oder</li>

<li>die alle möglichen Worte als Code umfassen: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=|\Sigma |^{n}}">

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=|\Sigma |^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b66ca2888b3b2a288bef11103a9b9c08fda34d92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.821ex; height:3.009ex;" alt="{\displaystyle |{\mathcal {C}}|=|\Sigma |^{n}}" loading="lazy">. Es lassen sich keine Übertragungsfehler erkennen, die übertragene Information ist aber maximal.</li></ul>

<th style="text-align:left">Bemerkungen:

</th></tr>

<tr>

<td>

<ul><li>Der erste Code lässt sich als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,0;2n+1,q]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,0;2n+1,q]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f84b1428e43878f36ed6ca90b5af60af2ad0a799.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.582ex; height:2.843ex;" alt="{\displaystyle [n,0;2n+1,q]}" loading="lazy">-Code schreiben. Er hat im klassischen Sinne keine Hamming-Distanz, da es keine Codepaare gibt. Es lassen sich bis zu maximal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f08b7e09d251558e937d42ac00924c0025c3ad64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.333ex; height:2.009ex;" alt="{\displaystyle t=n}" loading="lazy"> Symbolfehler im übertragenen Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> korrigieren (das übertragene Codewort ist bekannt), was eine typische Eigenschaft für Codes mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=2t+1=2n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=2t+1=2n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e8c889509b8234506b204d07eccad97c682d7e0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.978ex; height:2.343ex;" alt="{\displaystyle d=2t+1=2n+1}" loading="lazy"> ist. Das gleiche gilt für die Anzahl von Codes, die sich eindeutig dekodieren lassen. Die Gleichung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n}={\sum _{i=0}^{\lfloor (d-1)/2\rfloor }(q-1)^{i}{\binom {n}{i}}}}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n}={\sum _{i=0}^{\lfloor (d-1)/2\rfloor }(q-1)^{i}{\binom {n}{i}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1516c5f3e96c9d90b52185d8b6cfb08cfae9165.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:25.237ex; height:7.676ex;" alt="{\displaystyle q^{n}={\sum _{i=0}^{\lfloor (d-1)/2\rfloor }(q-1)^{i}{\binom {n}{i}}}}" loading="lazy"> liefert für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\geq 2n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\geq 2n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/229bddfa070bd0af57b3a41b7c3eb59c64dac145.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.874ex; height:2.343ex;" alt="{\displaystyle d\geq 2n+1}" loading="lazy"> das richtige Ergebnis.</li>

<li>Der zweite Code lässt sich als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,n;1,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,n;1,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7e1c55b0550bc74aac09c4fc0159c9cd3e70c0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.51ex; height:2.843ex;" alt="{\displaystyle [n,n;1,2]}" loading="lazy">-Code schreiben. Er hat eine Hamming-Distanz von 1.</li></ul>

</td></tr></tbody></table>

<a href="Linearer_Code" title="Linearer Code">Lineare Blockcodes</a> sind Codes, die auch als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-dimensionaler Untervektorraum von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e52398b6b9103472077e244c7db84eaeab4accdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{n}}" loading="lazy"> aufgefasst werden können. Es existiert dann eine Basis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1},\dots ,g_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1},\dots ,g_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/801375d568ed6292caa4f668207721e8d013a6f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.539ex; height:2.009ex;" alt="{\displaystyle g_{1},\dots ,g_{k}}" loading="lazy"> des Codes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy">.

Fasst man diese Basis zu einer <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrix</a>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{pmatrix}g_{1}\\g_{2}\\\vdots \\g_{k-1}\\g_{k}\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ef2a39a4d4c326eb54624b7b9f096803c0e0e299.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.005ex; width:14.042ex; height:17.176ex;" alt="{\displaystyle G={\begin{pmatrix}g_{1}\\g_{2}\\\vdots \\g_{k-1}\\g_{k}\end{pmatrix}}}" loading="lazy"></dd></dl>

zusammen, erhält man eine <a href="Generatormatrix" title="Generatormatrix">Generatormatrix</a> dieses linearen Blockcodes.

Die Codeworte erhält man durch Multiplizieren des Eingangssignals <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> mit der Generatormatrix

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)=x\cdot G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a09bc4c98bfc00effbee3cdf5df5ee8bc8bcc92a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.08ex; height:2.843ex;" alt="{\displaystyle c(x)=x\cdot G}" loading="lazy"></dd></dl>

Der Hauptvorteil linearer Code ist die einfache Codierbarkeit und die einfache Decodierbarkeit: Zur Kodierung eines Codes mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fc9b1525f5a653e19f9fd37fd2701a768e171632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.168ex; height:3.009ex;" alt="{\displaystyle q^{k}}" loading="lazy"> Codeworten muss man nur noch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Codeworte vorrätig halten. Gleiches gilt für die Dekodierung mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31246d3db82f98a975bd9d9a5ea525679f89ff6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.298ex; height:2.676ex;" alt="{\displaystyle q^{n}}" loading="lazy"> vs. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

<a href="Systematischer_Code" title="Systematischer Code">Systematische Blockcodes</a> sind Codes,

bei denen die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Informationssymbole direkt im Block ablesbar sind (meist am Blockanfang, siehe Abbildung am Anfang des Artikels).

Sie können gleichzeitig lineare Blockcodes sein, müssen es aber nicht.

Sie sind lineare Blockcodes, wenn neben den Informationssymbolen (die immer linear sind) auch die Prüfsymbole linear sind.

<a href="Perfekter_Code" title="Perfekter Code">Perfekte Blockcodes</a> sind Codes,

in denen jedes Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ef0581e4f7d507bcf8bc6593ccade369898bcec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.401ex; height:2.343ex;" alt="{\displaystyle w\in \Sigma ^{n}}" loading="lazy"> nur zu genau einem <a href="Code" title="Code">Codewort</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d67240ce3f564bd39e61e340509abe02b0373f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.087ex; height:2.176ex;" alt="{\displaystyle c\in {\mathcal {C}}}" loading="lazy"> (und nicht zu mehreren) einen geringsten <a href="Hamming-Abstand" title="Hamming-Abstand">Hamming-Abstand</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{w}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{w}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e8f34228ad0512bbf60d8a8c4e3a31ae32ac108c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.618ex; height:2.509ex;" alt="{\displaystyle d_{w}}" loading="lazy"> hat.

Jedes Wort lässt sich damit eindeutig decodieren. Der <a href="Hamming-Code" title="Hamming-Code">Hamming-Code</a> ist ein Beispiel für einen perfekten Code.

<a href="MDS-Code" title="MDS-Code">Maximum-Distanz-Codes</a> (MDS-Codes) sind Blockcodes,

deren Codeworte den größtmöglichen Hamming-Abstand voneinander haben. Beispiele für MDS Codes sind <a href="Wiederholungscode" title="Wiederholungscode">Wiederholungscodes</a>, <a href="Parit%C3%A4tsbit" title="Paritätsbit">Paritätscodes</a> und <a href="Reed-Solomon-Code" title="Reed-Solomon-Code">Reed-Solomon-Codes</a>.

<div class="mw-heading mw-heading2"><h2 id="Informationsrate_von_Blockcodes">Informationsrate von Blockcodes</h2></div>

Die <a href="Informationsrate" title="Informationsrate">Informationsrate</a> (auch Coderate) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> gibt an, wie viel Information pro Codewortsymbol im Mittel übertragen wird, sie ist also das Verhältnis von Nachrichtensymbolen zu Codewortsymbolen. Da ein Code Redundanz hinzufügt, gilt allgemein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq R\leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq R\leq 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f8aa1d06bfd3f405b088d2fa30712479e00ed30e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.286ex; height:2.343ex;" alt="{\displaystyle 0\leq R\leq 1}" loading="lazy">.

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4bac6e99f5cb83e2f634755e5be40520816641e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.234ex; height:2.509ex;" alt="{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}" loading="lazy"> ein Blockcode und es gelte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=|\Sigma |}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=|\Sigma |}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b97097334b2ead54b0ec3035dc095a11db878d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.14ex; height:2.843ex;" alt="{\displaystyle q=|\Sigma |}" loading="lazy">, das Alphabet habe also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> verschiedene Elemente. Dann lautet für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> die Definition der Informationsrate:

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\frac {\log _{q}(|{\mathcal {C}}|)}{\log _{q}(|\Sigma |^{n})}}={\frac {\log _{q}(|{\mathcal {C}}|)}{n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/29a2f1db559968499ea71eecc2bbe807134017d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:27.895ex; height:7.176ex;" alt="{\displaystyle R={\frac {\log _{q}(|{\mathcal {C}}|)}{\log _{q}(|\Sigma |^{n})}}={\frac {\log _{q}(|{\mathcal {C}}|)}{n}}}" loading="lazy">.</dd></dl>

Ist z. B. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> ein binärer Code mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> verschiedenen Codeworten, dann benötigt man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lceil \log _{2}s\rceil }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lceil \log _{2}s\rceil }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d18a026b18307ba9385463fa4fd1e90890eb7ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.568ex; height:2.843ex;" alt="{\displaystyle \lceil \log _{2}s\rceil }" loading="lazy"> Bits, um diese eindeutig zu unterscheiden.

Handelt es sich um einen linearen Code, so ist die Informationsrate:

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\frac {\log _{q}(q^{k})}{n}}={\frac {k}{n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/35367eb0d65cb0b44d7c7195e3e2ea4a27da69e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.966ex; height:6.176ex;" alt="{\displaystyle R={\frac {\log _{q}(q^{k})}{n}}={\frac {k}{n}}}" loading="lazy">.</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Beispiele_für_Blockcodes">Beispiele für Blockcodes</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Wiederholungscode">Wiederholungscode</h3></div>

<a href="Wiederholungscode" title="Wiederholungscode">Wiederholungscodes</a> sind lineare, systematische <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,1;n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,1;n]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/69582b51f15eae9774e480a48572c089e8c3d079.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.313ex; height:2.843ex;" alt="{\displaystyle [n,1;n]}" loading="lazy">-Blockcodes über einem beliebigen Alphabet, bei denen jedes Nachrichtensymbol n-mal wiederholt wird. Damit hat ein Wiederholungscode die Generatormatrix

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{pmatrix}1\cdots 1\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4475c45fa0deeb0fe73acb5bb6a4ed460b639af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.308ex; height:2.843ex;" alt="{\displaystyle G={\begin{pmatrix}1\cdots 1\end{pmatrix}}}" loading="lazy">

und eine Informationsrate von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R={\frac {1}{n}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\frac {1}{n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f935535a7aa07a69b7f1b4a69c7f1f452090406.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.093ex; height:5.176ex;" alt="{\displaystyle R={\frac {1}{n}}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Paritätscode">Paritätscode</h3></div>

<a href="Parit%C3%A4tsbit" title="Paritätsbit">Paritätscodes</a> (engl. Single Parity Check (SPC) codes) sind lineare, systematische und binäre Codes, bei denen der Nachricht ein einziges Prüfbit angefügt wird, das sich als XOR-Verknüpfung aller Nachrichtenbits ergibt. Somit hat jedes Codewort eine gerade Anzahl an „1“-Bits. Die Generatormatrix hat folgende Form:

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{pmatrix}10\dots 00\,\,1\\01\dots 00\,\,1\\\,\,\,\,\vdots \ddots \vdots \,\,\,\,\,\,\vdots \\00\dots 10\,\,1\\00\dots 01\,\,1\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/60982d21c1eab5b9410ce95855dc235d7e61f7ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.171ex; width:19.827ex; height:17.509ex;" alt="{\displaystyle G={\begin{pmatrix}10\dots 00\,\,1\\01\dots 00\,\,1\\\,\,\,\,\vdots \ddots \vdots \,\,\,\,\,\,\vdots \\00\dots 10\,\,1\\00\dots 01\,\,1\\\end{pmatrix}}}" loading="lazy">

Sie haben eine Hamming-Distanz von 2 und stellen -<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,n-1;2,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,n-1;2,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/93bbf225c188431ee101755866c8395269bf34bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.513ex; height:2.843ex;" alt="{\displaystyle [n,n-1;2,2]}" loading="lazy">Blockcodes dar. Sie können einen Fehler erkennen, aber keine Fehler korrigieren.

Lineare binäre Blockcodes mit ungeradem Hamming-Abstand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k;2m+1,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k;2m+1,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/488baf6174c9652ca5a90f1bee8681d133c52ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.37ex; height:2.843ex;" alt="{\displaystyle [n,k;2m+1,2]}" loading="lazy"> lassen sich mit einem zusätzlichen Paritätscode zu einem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n+1,k;2m+2,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n+1,k;2m+2,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/29a4c4cf60df25a020f20df4b87a13958f6865ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.372ex; height:2.843ex;" alt="{\displaystyle [n+1,k;2m+2,2]}" loading="lazy">-Code erweitern.

<div class="mw-heading mw-heading3"><h3 id="Hadamard-Code">Hadamard-Code</h3></div>

<a href="Hadamard-Code" title="Hadamard-Code">Hadamard Codes</a> sind lineare nicht-systematische Blockcodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{k},k+1;2^{k-1}]}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{k},k+1;2^{k-1}]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ba688a56615b0eeb877852f5eebb3c34da89e21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.179ex; height:3.176ex;" alt="{\displaystyle [2^{k},k+1;2^{k-1}]}" loading="lazy">. Die Generatormatrix hat eine sehr auffällige Form

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{pmatrix}01010101\cdots 10\cdots 01010101\\00110011\cdots 10\cdots 00110011\\00001111\cdots 10\cdots 00001111\\\vdots \\00000000\cdots 01\cdots 11111111\\11111111\cdots 10\cdots 00000000\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99609737db65e6b3aec8134a7e9463507c9e7b7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.505ex; width:37.663ex; height:20.176ex;" alt="{\displaystyle G={\begin{pmatrix}01010101\cdots 10\cdots 01010101\\00110011\cdots 10\cdots 00110011\\00001111\cdots 10\cdots 00001111\\\vdots \\00000000\cdots 01\cdots 11111111\\11111111\cdots 10\cdots 00000000\\\end{pmatrix}}}" loading="lazy"></dd></dl>

Sie haben eine geringe Coderate von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R={\frac {k+1}{2^{k}}}}">

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\frac {k+1}{2^{k}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0f65e982c3ab1b8f8df3d5652de461ff302cf741.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:10.913ex; height:5.843ex;" alt="{\displaystyle R={\frac {k+1}{2^{k}}}}" loading="lazy">, können aber noch Daten aus sehr fehlerbehafteten Signal dekodieren. Daher fanden sie unter anderem in der <a href="Mariner" title="Mariner">Mariner 9 Mission</a> Anwendung.

<div class="mw-heading mw-heading3"><h3 id="Weitere_Beispiele_für_Blockcodes">Weitere Beispiele für Blockcodes</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Beispiel_1">Beispiel 1</h4></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (9,\{0,31,227,364,437,474\};5,2)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/51d2c1cb0ef89427e1a9f53c7efdfca178842c6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.33ex; height:2.843ex;" alt="{\displaystyle (9,\{0,31,227,364,437,474\};5,2)}" loading="lazy"></dd></dl>

Die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=6}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=6}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67ad96b7476d4f0e5862bded2ed058383d56d517.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.794ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {C}}|=6}" loading="lazy"> Codeworte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> lauten in der Binärdarstellung:

<pre>.........

....#####

.###...##

#.##.##..

##.##.#.#

###.##.#.

</pre>

Es existiert kein linearer Code dieser Mächtigkeit.

Zum einen ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{log}}_{q}6\not \in \mathbb {N} ^{+}}">

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{log}}_{q}6\not \in \mathbb {N} ^{+}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c98a3f58348f209e45037d09738d05af81ee2f2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.152ex; height:3.343ex;" alt="{\displaystyle {\text{log}}_{q}6\not \in \mathbb {N} ^{+}}" loading="lazy">, zum anderen sind die größten lineare Code dieser Art ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [8,2;5,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [8,2;5,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d8145ed7ad6fdb124e2057f9649a3b06c63e7393.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.045ex; height:2.843ex;" alt="{\displaystyle [8,2;5,2]}" loading="lazy">- und ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [10,3;5,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [10,3;5,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fda2367e6c46e70d280fa9c0676e2c153dea4e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.208ex; height:2.843ex;" alt="{\displaystyle [10,3;5,2]}" loading="lazy">-Code. Der Code lässt sich nicht in einen linearen Code umwandeln.

<div class="mw-heading mw-heading4"><h4 id="Beispiel_2">Beispiel 2</h4></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (11,\{0,143,307,444,597,730,870,1001,1130,1253,1369,1494,1599,1712,1804,1923\};5,2)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ac9ecdcfa6de4c98d40d60955500781c542a8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:91.33ex; height:2.843ex;" alt="{\displaystyle (11,\{0,143,307,444,597,730,870,1001,1130,1253,1369,1494,1599,1712,1804,1923\};5,2)}" loading="lazy"></dd></dl>

Die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=16}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=16}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb4240e58a09957bdef1563d4b588cfe09a14648.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.956ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {C}}|=16}" loading="lazy"> Codeworte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> lauten in der Binärdarstellung (MSB links):

<pre>...........

...#...####

..#..##..##

..##.####..

.#..#.#.#.#

.#.##.##.#.

.##.##..##.

.#####.#..#

#...##.#.#.

#..###..#.#

#.#.#.##..#

#.###.#.##.

##...######

##.#.##....

###....##..

####.....##

</pre>

Es handelt sich um einen linearen systematischen Code mit der Basis

<pre>...#...####

..#..##..##

.#..#.#.#.#

#...##.#.#.

</pre>

Die 16 Codeworte lassen sich durch eine XOR-Verknüpfung der Basisvektoren erzeugen, deren Informationsbits gesetzt sind (daher linearer Code). Die Informationsbits stellen die linken 4 Bit dar (Bit 10 bis 7), die Schutzbits die rechten 7 Bit (Bit 6 bis 0) (daher systematischer Code).

<div class="mw-heading mw-heading4"><h4 id="Beispiel_3">Beispiel 3</h4></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (8,\{0,7,25,30,42,53,75,84,97,108,114,127,140,147,166,169,176,194,197,216\};3,2)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61ffc38d90694cfd4734ee306789534f759610c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:87.329ex; height:2.843ex;" alt="{\displaystyle (8,\{0,7,25,30,42,53,75,84,97,108,114,127,140,147,166,169,176,194,197,216\};3,2)}" loading="lazy"></dd></dl>

Die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=20}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=20}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a005901b41bcec6923a94491054244e3f863f32a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.956ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {C}}|=20}" loading="lazy"> Codeworte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> lauten in der Binärdarstellung:

<pre>........

.....###

...##..#

...####.

..#.#.#.

..##.#.#

.#..#.##

.#.#.#..

.##....#

.##.##..

.###..#.

.#######

#...##..

#..#..##

#.#..##.

#.#.#..#

#.##....

##....#.

##...#.#

##.##...

</pre>

Es existiert kein linearer Code dieser Mächtigkeit.

Auch hier ist zum einen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{log}}_{q}20\not \in \mathbb {N} ^{+}}">

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{log}}_{q}20\not \in \mathbb {N} ^{+}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8283f590146095ebe778e4f6716fb478b7065462.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.315ex; height:3.343ex;" alt="{\displaystyle {\text{log}}_{q}20\not \in \mathbb {N} ^{+}}" loading="lazy">, zum anderen sind die größten lineare Code dieser Art ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [7,4;3,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [7,4;3,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c0b6b3e082a3ae82b89c00ac768a27c73dc1bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.045ex; height:2.843ex;" alt="{\displaystyle [7,4;3,2]}" loading="lazy">- und ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [9,5;3,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [9,5;3,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68aea8e185236ce75f09d771b304f31049062cf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.045ex; height:2.843ex;" alt="{\displaystyle [9,5;3,2]}" loading="lazy">-Code. Der Code lässt sich nicht in einen linearen Code umwandeln.

<div class="mw-heading mw-heading2"><h2 id="Fehlerkorrektur">Fehlerkorrektur</h2></div>

Blockcodes können zur <a href="Fehlerkorrekturverfahren" title="Fehlerkorrekturverfahren">Fehlererkennung und Fehlerkorrektur</a> bei der Übertragung von Daten über fehlerbehaftete <a href="Kanal_(Informationstheorie)" title="Kanal (Informationstheorie)">Kanäle</a> verwendet werden. Dabei ordnet der Sender dem zu übertragenen Informationswort der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> ein Codewort der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> zu, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n>k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8afbc0693bee3f48a31d2c991ddc8b6b4a35322.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.704ex; height:2.176ex;" alt="{\displaystyle n>k}" loading="lazy">. Durch das Hinzufügen der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b98e1d6a69bccd09a4b9b69bdf03a08c1706c8c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.446ex; height:2.343ex;" alt="{\displaystyle n-k}" loading="lazy"> zusätzlichen Symbole entsteht <a href="Redundanz_(Informationstheorie)" title="Redundanz (Informationstheorie)">Redundanz</a> und die Informationsrate sinkt; jedoch kann der Empfänger die redundante Information nun dazu nutzen Übertragungsfehler zu erkennen und zu korrigieren.

Verwendet man beispielsweise, im Fall der Binärkodierung, die Zuordnung

<th>Informationswort

</th>

<th>Codewort

</th></tr>

<tr>

<td>0

</td>

<td>000

</td></tr>

<tr>

<td>1

</td>

<td>111

</td></tr></tbody></table>

so können empfangene Codewörter mit genau einem Bitfehler korrigiert werden, indem man mit Hilfe einer <a href="Boolesche_Funktion#Beispiel_Mehrheits-Funktion" title="Boolesche Funktion">Mehrheitsfunktion</a> das abweichende Bit umkehrt:

<th>Fehlerhaftes Codewort

</th>

<th>Korrigiertes Codewort

</th>

<th>Zugeordnetes Informationswort

</th></tr>

<tr>

<td>001

</td>

<td>000

</td>

<td>0

</td></tr>

<tr>

<td>010

</td>

<td>000

</td>

<td>0

</td></tr>

<tr>

<td>011

</td>

<td>111

</td>

<td>1

</td></tr>

<tr>

<td>100

</td>

<td>000

</td>

<td>0

</td></tr>

<tr>

<td>101

</td>

<td>111

</td>

<td>1

</td></tr>

<tr>

<td>110

</td>

<td>111

</td>

<td>1

</td></tr></tbody></table>

Sind in diesem Falle jedoch zwei Bits falsch, so wird zwar ein Fehler erkannt, aber fehlerhaft korrigiert. Sind gar drei Bits falsch, so kann nicht einmal mehr ein Fehler erkannt werden.

<div class="mw-heading mw-heading2"><h2 id="Schranken">Schranken</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Singleton-Schranke">Singleton-Schranke</h3></div>

Die <a href="Singleton-Schranke" title="Singleton-Schranke">Singleton-Schranke</a> bezeichnet eine obere Schranke für die <a href="Hamming-Abstand#Mindestdistanz" title="Hamming-Abstand">Mindestdistanz</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> eines Blockcodes der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> bei Informationswörtern der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> über einem einheitlichen Alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy">.

Sie lautet:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\leq n-k+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d554ddcf246d03db4f7cbe0f80ac3e9111037549.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.764ex; height:2.343ex;" alt="{\displaystyle d\leq n-k+1}" loading="lazy"></dd></dl>

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

<ul><li>Annahme: Alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma =\{0,\ldots ,q-1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma =\{0,\ldots ,q-1\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/675d835f37e82f1c112ab7c4f56e72ec6e0877bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.515ex; height:2.843ex;" alt="{\displaystyle \Sigma =\{0,\ldots ,q-1\}}" loading="lazy"></li>

<li>Anzahl der möglichen Informationswörter: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {I}}|=q^{k}}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {I}}|=q^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4d91bb9e93dc705a236d9b32e7134e62c2dd8d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.053ex; height:3.176ex;" alt="{\displaystyle |{\mathcal {I}}|=q^{k}}" loading="lazy"></li>

<li>Anzahl der Codewörter: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=|{\mathcal {I}}|=q^{k}}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=|{\mathcal {I}}|=q^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f02f3da9841c6d2fd6889e8499f4c14676c78fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.684ex; height:3.176ex;" alt="{\displaystyle |{\mathcal {C}}|=|{\mathcal {I}}|=q^{k}}" loading="lazy"></li>

<li>Mindestdistanz: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"></li></ul>

Streicht man nun in den Codewörtern jeweils die letzten (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy">) der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Stellen, so haben die übrigen Codewörter zueinander immer noch mindestens den <a href="Hamming-Abstand" title="Hamming-Abstand">Hamming-Abstand</a> 1. Bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> Streichungen wäre dies nicht mehr gewährleistet. Damit sind immer noch alle Codewörter unterschiedlich, also

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}'|=|{\mathcal {C}}|=q^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea037208a3a6b3f7ab5bf5dd89157efbfe500843.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.12ex; height:3.176ex;" alt="{\displaystyle |{\mathcal {C}}'|=|{\mathcal {C}}|=q^{k}}" loading="lazy"></dd></dl>

Deswegen muss auch die Anzahl der durch die Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-(d-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-(d-1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ebf8982fccdccff0d042a4482912789db8e66bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.263ex; height:2.843ex;" alt="{\displaystyle n-(d-1)}" loading="lazy"> erzeugbaren Wörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n-d+1}\geq q^{k}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n-d+1}\geq q^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fcaf0f2e95ecf7cd3381b0288d407c34613b400b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.803ex; height:3.009ex;" alt="{\displaystyle q^{n-d+1}\geq q^{k}}" loading="lazy"> sein. Stellt man diese Gleichung um, ergibt sich daraus die Singleton-Schranke

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-d+1\geq k\Leftrightarrow d\leq n-k+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac7b8de779f2e31a26d6a34da47d2597bb8b4bc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:31.141ex; height:2.343ex;" alt="{\displaystyle n-d+1\geq k\Leftrightarrow d\leq n-k+1}" loading="lazy"></dd></dl>

Für nicht-lineare Codes gilt entsprechend

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\leq q^{n-d+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e877bbbc7e839d7ca37ed8ea4dc2779dd37117f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.077ex; height:3.009ex;" alt="{\displaystyle M\leq q^{n-d+1}}" loading="lazy">,</dd></dl>

wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M=|{\mathcal {C}}|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=|{\mathcal {C}}|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/84e99005b0c893ba684f5c0a59fd6405f6b7aaaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.073ex; height:2.843ex;" alt="{\displaystyle M=|{\mathcal {C}}|}" loading="lazy">.

Codes, die die Singleton-Schranke mit Gleichheit erfüllen, nennt man auch <a href="MDS-Code" title="MDS-Code">MDS-Codes</a>.

Im Falle der <a href="Hamming-Schranke" class="mw-redirect" title="Hamming-Schranke">Hamming-Schranke</a> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=\lfloor (d-1)/2\rfloor }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=\lfloor (d-1)/2\rfloor }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/be72915a7351e7ce03c0ee39347abd0b1c76cc9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.356ex; height:2.843ex;" alt="{\displaystyle t=\lfloor (d-1)/2\rfloor }" loading="lazy"> die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming-Distanz <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">.

Die Hamming-Schranke sagt aus, dass

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n}\geq q^{k}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f67f295927f48eaf61518be010612adc14f4d4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:23.417ex; height:7.176ex;" alt="{\displaystyle q^{n}\geq q^{k}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}" loading="lazy">,</dd></dl>

beziehungsweise

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq k+\log _{q}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/950fddbd326a13e5a14c8c6771408dbea048c639.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:28.744ex; height:7.176ex;" alt="{\displaystyle n\geq k+\log _{q}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}" loading="lazy"></dd></dl>

erfüllt sein muss für einen Code, der mittels <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Symbolen eines Alphabets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> der Größe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> eine Nachricht mit der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> transportiert.

Die Singleton-Schranke ist eine ungenauere Abschätzung als die Hamming-Schranke, die die Größe des Alphabets nicht berücksichtigt. Weiterhin gibt es Unterschiede in der Beziehung zwischen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Plotkin-Grenze">Plotkin-Grenze</h3></div>

In der <a href="Kanalcodierung" class="mw-redirect" title="Kanalcodierung">Kanalcodierung</a> verwendet man Blockcodes, um Fehler in Datenströmen erkennen und korrigieren zu können. Ein Blockcode <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> über einem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">-nären Alphabet mit einem Minimalabstand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> erfüllt die <a href="Plotkin-Grenze" title="Plotkin-Grenze">Plotkin-Grenze</a>, auch als Plotkin-Schranke bezeichnet,<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

</mrow>

</mrow>

<mfrac>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |C|\leq {\frac {d}{d-({\frac {q-1}{q}})\cdot n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf807806db847058e8b19397464b69e6a8d0c767.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:19.627ex; height:7.343ex;" alt="{\displaystyle |C|\leq {\frac {d}{d-({\frac {q-1}{q}})\cdot n}}}" loading="lazy"></dd></dl>

dann, wenn der Nenner positiv ist. Somit liefert die Plotkin-Grenze nur dann ein Resultat, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> hinreichend nahe bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> liegt.

Nimmt ein Code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> die Plotkin-Schranke an, so gilt insbesondere, dass der Abstand zweier beliebiger Codewörter genau <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> ist.

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\geq 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\geq 3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6a54291981721fe18de52607871df1c42ec22629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q\geq 3}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |C|=a\cdot q+b}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |C|=a\cdot q+b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/154912fd33fce2968c0de64c906b68d8665304ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.975ex; height:2.843ex;" alt="{\displaystyle |C|=a\cdot q+b}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b<q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/36613164125a07425d01be6caacad31da6a219fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.166ex; height:2.509ex;" alt="{\displaystyle b<q}" loading="lazy">, so gilt sogar die schärfere Beziehung:<a href="#cite_note-3">[3]</a>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

<mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d{|C| \choose 2}\leq n\left({|C| \choose 2}-b{a+1 \choose 2}-(q-b){a \choose 2}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/223a3ef4e3a454cc7d1d839b8d14b0004880c5c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:49.18ex; height:6.176ex;" alt="{\displaystyle d{|C| \choose 2}\leq n\left({|C| \choose 2}-b{a+1 \choose 2}-(q-b){a \choose 2}\right)}" loading="lazy"></dd></dl>

Beispielsweise liefert die Plotkin-Grenze für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d859ff2e5023ed1f714ccace69e88ab993a5f43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=3}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=9}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=9}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1029ce8384fde9f4da54009c5a79f17a9758085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=9}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=7}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=7}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a608ac8e786da673f07f9647c4787e4bfdd4ee9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.477ex; height:2.176ex;" alt="{\displaystyle d=7}" loading="lazy"> nur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |C|\leq 7}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |C|\leq 7}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a9d51b99aa367c8f57c9d39a7dfb7e44b6bf2a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.321ex; height:2.843ex;" alt="{\displaystyle |C|\leq 7}" loading="lazy">, die Verschärfung jedoch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |C|\leq 6}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |C|\leq 6}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/113351a461b83ad04031ccbc579b940b919e1b55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.321ex; height:2.843ex;" alt="{\displaystyle |C|\leq 6}" loading="lazy">, da sich für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4208bf5a67fc2ceb3a3bcd75aebb1d74fbb531bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a=2}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3f55bc77dec8088791b5c1ed51e634cc1b431fd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.258ex; height:2.176ex;" alt="{\displaystyle b=1}" loading="lazy"> ein Widerspruch ergibt.

Sie wurde 1960 von Morris Plotkin veröffentlicht.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Rudolf Nocker: Digitale Kommunikationssysteme 1. Grundlagen der Basisbandübertragung, 1. Auflage, Friedrich Vieweg & Sohn Verlag, Wiesbaden 2004, ISBN 978-3-528-03976-9.</li>

<li>Markus Hufschmid: Information und Kommunikation. Grundlagen der Informationsübertragung, Vieweg und Teubner, Wiesbaden 2006, ISBN 3-8351-0122-6.</li>

<li>Bernd Friedrichs: Kanalcodierung. Grundlagen und Anwendungen in modernen Kommunikationssystemen. Springer Verlag, Berlin/Heidelberg 1995, ISBN 3-540-59353-5.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20180406163859/https://home.zhaw.ch/~rur/ntm/unterlagen/ntmkap94itfec1.pdf">Kanalcodierung und Blockcodes</a></li>

<li><a rel="nofollow" class="external text" href="http://www.inf.fu-berlin.de/lehre/SS09/PI02/docs/codierungstheorie_Teil1.pdf">Proinformatik - Funktionale Programmierung</a> (abgerufen am 6. April 2018)</li>

<li><a rel="nofollow" class="external text" href="http://ecee.colorado.edu/~mathys/ecen5682/slides/blockperf99.pdf">Theory and Practice of Error Control Codes Block Code Performance</a> (abgerufen am 6. April 2018)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> M. Plotkin: Binary codes with specified minimum distance, IRE Transactions on Information Theory, 6:445-450, 1960 (engl.).

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> W.C. Huffman, V. Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003 (engl.).

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> <a rel="nofollow" class="external text" href="http://www.combinatorics.org/Volume_10/Abstracts/v10i1n6.html">Die Plotkin-Grenze und ihre Verschärfung</a> (englisch).

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-10-27" href="https://de.wikipedia.org/wiki/?title=Blockcode&oldid=249809863">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>